Flatten nested list iterator [Iterator]

Time: O(N); Space: O(H); medium

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Example 1:

Input: nestedList = [[1,1],2,[1,1]]

Output: [1,1,2,1,1]

Explanation:

• By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

Input: nestedList = [1,[4,[6]]]

Output: [1,4,6]

Explanation:

• By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

Notes:

• N is the Number of the integers

• H is the depth of the nested lists

"""
This is the interface that allows for creating nested lists.
You should not implement it, or speculate about its implementation
"""
class NestedInteger(object):
    def isInteger(self):
        """
        :rtype bool
        Return True if this NestedInteger holds a single integer, rather than a nested list.
        """

    def getInteger(self):
        """
        :rtype int
        Return the single integer that this NestedInteger holds,
        if it holds a single integer
        Return None if this NestedInteger holds a nested list
        """

    def getList(self):
        """
        :rtype List[NestedInteger]
        Return the nested list that this NestedInteger holds,
        if it holds a nested list
        Return None if this NestedInteger holds a single integer
        """

class NestedIterator1(object):

    def __init__(self, nestedList):
        """
        :type nestedList: List[NestedInteger]
        """
        self.__depth = [[nestedList, 0]]

    def next(self) -> int:
        nestedList, i = self.__depth[-1]
        self.__depth[-1][1] += 1
        # return nestedList[i].getInteger()
        return int(nestedList[i])

    def hasNext(self) -> bool:
        while self.__depth:
            nestedList, i = self.__depth[-1]
            if i == len(nestedList):
                self.__depth.pop()
            # elif nestedList[i].isInteger():
            elif isinstance(nestedList[i], int):
                return True
            else:
                self.__depth[-1][1] += 1
                # self.__depth.append([nestedList[i].getList(), 0])
                self.__depth.append([nestedList[i], 0])
        return False

# Your NestedIterator object will be instantiated and called as such:
nestedList = [[1,1],2,[1,1]]
s, res = NestedIterator1(nestedList), []
while s.hasNext():
    res.append(s.next())
assert res == [1,1,2,1,1]

nestedList = [1,[4,[6]]]
s, res = NestedIterator1(nestedList), []
while s.hasNext():
    res.append(s.next())
assert res == [1,4,6]

See also:

https://leetcode.com/problems/flatten-nested-list-iterator

https://www.lintcode.com/problem/flatten-nested-list-iterator